package algorithms.sort;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @description: 手写排序算法
 *          时间复杂度：N*log(N)级别:
 *         1.快速排序 {@link SortUtils#quickSort(int[])}
 *         2.归并排序 {@link SortUtils#mergeSort(int[])}
 *         3.堆排序 {@link SortUtils#heapSort(int[])}
 *
 *
 * @author: zk
 * @date: 2024-02-04
 */
public class SortUtils {

    public static void main(String[] args) {
        int[] arr = {100, 23, 12, 3, 23, 6, 9, 2, 2, 4, 2, 123, 543, 12};
        //mergeSort(arr);
//        quickSort(arr);
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 交换,下标的值
     *
     * @param arr
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // -----------------------快速排序 start---------------------------
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 核心: 随机选取一个下标作为比较值,将原来的数组构建 [ < 区域 | = 区域 | > 区域] 的数组，
     * 此时=区域就已经排好序了;再递归左边,右边区域就完成整体有序;
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 随机选择下标放到最后,构成数学的等概率事件
            swap(arr, ThreadLocalRandom.current().nextInt(left, right), right);

            // 构建 [ < 区域 | = 区域 | > 区域] 的数组
            int[] eqIndexArr = partition(arr, left, right);
            // 左边继续
            quickSort(arr, left, eqIndexArr[0] - 1);
            // 右边继续
            quickSort(arr, eqIndexArr[0] + 1, right);
        }
    }

    /**
     * 将数组弄成 [ < 区域 | = 区域 | > 区域] 的数组
     *
     * @param arr   : [。。。。| 最后一位是比较的数字 ] 的数组
     * @param left
     * @param right
     * @return 返回等于区域的 左下标 和 右下标
     */
    private static int[] partition(int[] arr, int left, int right) {
        // 两个指针,指向 <区域 和 >区域 的下标。
        int lt = left - 1;
        // 最后一位放比较的数
        int gt = right;

        for (int i = left; i < gt; ) {
            if (arr[i] < arr[right]) {
                // [i] < 最后一位,小于区域扩展,i++;
                swap(arr, ++lt, i++);
            } else if (arr[i] == arr[right]) {
                // [i] == 最后一位,i++;
                i++;
            } else {
                // [i] > 最后一位,交换到 >区 的位置,大于区域扩展 @FIXME i不变是因为交换过来的值是未知的,等下一次进行比较）
                swap(arr, i, --gt);
            }
        }
        // 将比较的数字放在 >区 的前一位
        swap(arr, right, gt);
        // 返回等于区域的 左下标 和 右下标
        return new int[]{lt + 1, gt};
    }

    // -----------------------快速排序 end---------------------------


    // -----------------------归并排序 start---------------------------
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 归并排序: 局部有序-->整体有序
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void mergeSort(int[] arr, int left, int right) {
        // 只有一个数,停止
        if (left == right) {
            return;
        }
        // 中点
        int mid = left + ((right - left) >> 1);
        // 左边排序,右边排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    /**
     * 比较两个数组的大小,合并为一个数组
     * 举例,下标
     * [0,1,2,3,4]
     * |   |   |
     * l   m   r
     * <p>
     * 举例:两个数组,数值形式: [1,5] , [6,3,7]
     * |       |
     * p1     p2
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        // 额外的辅助空间,保存比较的值
        int[] help = new int[right - left + 1];
        int helpIndex = 0;

        // 双指针,开始指向两个数组的开始位置
        int p1 = left;
        int p2 = mid + 1;

        // 1.不越界进行比较,谁小拷贝谁,相等拷贝左边数组的内容;
        while (p1 <= mid && p2 <= right) {
            help[helpIndex++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 2.比较完毕后将剩下的进行拷贝,以下while只会有一个执行
        while (p1 <= mid) {
            help[helpIndex++] = arr[p1++];
        }
        while (p2 <= right) {
            help[helpIndex++] = arr[p2++];
        }

        // 3.将排好序的help数组拷贝回到原位置
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }

    // -----------------------归并排序 end---------------------------

    // -----------------------堆排序 start---------------------------

    public static void heapSort(int[] arr) {
        heapSort(arr, 0, arr.length - 1);
    }

    /**
     * 使用使用堆结构: 将所有数依次入堆后,在依次出堆。
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void heapSort(int[] arr, int left, int right) {
        Heap heap = new Heap(arr.length);
        // 构建大根堆,默认是小根堆

        // 入大根堆
        for (int i = left; i <= right; i++) {
            heap.insert(arr[i]);
        }

        // 出堆
        while (!heap.isEmpty()) {
            arr[right--] = heap.remove();
        }

        /*
        // 使用JDK的堆做排序
        // 构建大根堆,默认是小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(arr.length,(o1,o2)-> o2 - o1);

        // 入大根堆
        for (int i = left; i <= right; i++) {
            heap.add(arr[i]);
        }

        // 出堆
        while (!heap.isEmpty()) {
            arr[right--] = heap.remove();
        }
         */
    }

    // -----------------------堆排序 end---------------------------


}
